import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    public char val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(char val) {
        this.val = val;
    }
}

public class Test {


    public static int i=0;
    //    创建树
    public static TreeNode createTree(String str) {
        TreeNode root=null;
        if(str.charAt(i)!='#') {
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=createTree(str);
            root.right=createTree(str);
        }else {
            //空树，直接++
            i++;
        }
        return root;
    }

//    层序遍历
    public void levelOrder(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null) {
            return;
        }
        queue.offer(root);
        while(!queue.isEmpty()) {
            //将当前节点保存在cur中
            TreeNode cur=queue.poll();
            //并打印
            System.out.print(cur.val+" ");

            //压入左右子节点
            if(cur.left!=null) queue.offer(cur.left);
            if(cur.right!=null)queue.offer(cur.right);
        }
        System.out.println();
    }

//    public List<List<Integer>> levelOrder2(TreeNode root) {
//        List<List<Integer>> ret=new ArrayList<>();
//        if(root==null)return ret;
//        Queue<TreeNode> queue=new LinkedList<>();
//        queue.offer(root);
//
//        while(!queue.isEmpty()) {
//            int size=queue.size();
//            List<Integer> list=new ArrayList<>();
//
//            while(size>0) {
//                TreeNode cur=queue.poll();
//                list.add(cur.val);
//                if(cur.left!=null) queue.offer(cur.left);
//                if(cur.right!=null) queue.offer(cur.right);
//                size--;
//            }
//            ret.add(list);
//        }
//        return ret;
//    }
}
